import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class FourSum {
    class Solution {
        public List<List<Integer>> fourSum(int[] nums, int target) {

            Arrays.sort(nums);
            List<List<Integer>> res = new ArrayList<>();
            for(int i = 0 ; i < nums.length ; i ++)
            {


                // 注意这里不能说nums[i] > target 就返回了
                // 例如target 是负数的话就会出错
                // -11 【-5，-4，-2】  nums[i] > -11 直接返回错误结果

                if(i > 0 && nums[i] == nums[i-1])continue;
                for(int k = i + 1; k < nums.length ; k ++)
                {
                    if(k > i + 1 && nums[k] == nums[k-1]) continue;
                    int left = k + 1;
                    int right = nums.length -1;

                    while(left < right)
                    {

                        long sum = (long)nums[i] + nums[k] + nums[left] + nums[right];

                        if (sum < target)
                        {
                            left ++;
                        }else if(sum > target )
                        {
                            right --;
                        }else{
                            List<Integer> tmp = new ArrayList<>();
                            tmp.add(nums[i]);
                            tmp.add(nums[k]);
                            tmp.add(nums[left]);
                            tmp.add(nums[right]);
                            res.add(tmp);
                            while(left < right && nums[right] == nums[right - 1]) right--;
                            while(left < right && nums[left] == nums[left + 1]) left ++;
                            left ++;
                            right --;

                        }
                    }


                }

            }

            return res;
        }



    }


}
